#include	<stdio.h>
#include	<stdlib.h>

#define	T  short/*  */
#if 0
int mergeSort(T *x, T *y, int n) 
{
    int step = 1;
    T *src = y, *dst = x, *temp;
    int i , jj, k;
    int ilimit, jlimit;

    for (step = 1; step < n; step *= 2) 
    {
       temp = src; src = dst; dst = temp;
       //attention the move step of i is 2 * step
       for (i = 0, jj = step; jj < n; i = jlimit, jj = i+step) 
       {
           k = i;
           ilimit = jj;
           jlimit = jj + step;
           //must be less than n
           if (jlimit > n)
               jlimit = n;
           while (i < ilimit && jj < jlimit) 
           {
               if (src[i] <= src[jj])
                   dst[k++] = src[i++];
               else 
                   dst[k++] = src[jj++];
           }
           while (i < ilimit)
               dst[k++] = src[i++];
           while (jj < jlimit)
               dst[k++] = src[jj++];
       }
       //copy the data that has not been compared
       while (i < n)
           dst[k++] = src[i++];
//       printf ( "step %d\n", step );
//       for (i = 0; i < n; ++i)
//       {
//           printf ( "%d(%d)\t", dst[i], src[i]);
//       }
//       printf ( "\n" );
    }

    if (dst == x)
        return 0;
    return 1;
}

int cmp(const void *p1, const void * p2)
{
    return *(const T*)p1 - *(const T*)p2;
}

#endif

void bubble_sort(T *x, int n)
{
    char changed = 0;
    T tmp;
    int k, idx;
    for (idx = n-1; idx > 0; --idx)
    {
        changed = 0;
        for (k = 0; k < idx; ++k)
        {
            if (x[k+1] < x[k]) {
                tmp = x[k];
                x[k] = x[k+1];
                x[k+1] = tmp;
                changed = 1;
            }
        }
        if (changed == 0)
            break;
    }
}

int main()
{
    short v[1000];
    int   TT;
    int   N,n,value,sum = 0;
    int x, y;
    int i, flag = 0;
    scanf("%d", &TT);
    while (TT--) {
        scanf("%d", &N);
        for (i = 0; i < N; ++i)
        {
            scanf("%d", &value);
            v[i] = value;
            //v[0][i] = value;
        }
        //qsort(v, N, sizeof(T), cmp);
        bubble_sort(v, N);
        //i = mergeSort(v[0], v[1], N);
        n = N; flag = 0; sum = 0;
        //where to begin is import, from the most slowest
        //adopt two stratgies, whether use the fastest, or the two slowest at one time
        //the former stratgy is caculated with y, and the later with x below
        while (n >= 4)
        {
            y = 2 * v[0] + v[n-1] + v[n-2];
            if (flag == 0) {
                x = v[0] + 2 * v[1] + v[n-1];
                if (y <= x) flag = 1;
                else  y = x;
            }
            sum += y;
            n -= 2;
        }
        if (n == 1 || n == 2)
            sum += v[n-1];
        else if (n == 3)
            sum += (v[0]+v[1]+v[2]);
        printf ( "%d\n", sum);
    }
    return 0;
}
